1. Field of the Invention
The present invention relates generally to the field of modeling smooth free-form shapes for computer graphics applications and the like. More particularly, the present invention relates to a system and method for generating smooth low degree polynomial spline surfaces over irregular meshes.
2. Description of Related Art
Geometric modeling has emerged as the primary technique used to describe the shape of an object or to simulate dynamic processes. Much of the power of contemporary geometric modeling resides in its techniques for synthesizing, and allowing easy description of complex shapes as arrangements of simpler ones. The importance of geometric modeling is rapidly increasing in many fields. It is a primary ingredient in computer-aided design (CAD) and computer-aided manufacturing (CAM) systems, computer graphics, computer art, animation, simulation, computer vision, and robotics. Advances in any of these fields depend on how well effective geometric models can be generated.
The construction of geometric models itself is usually a computer-aided operation, with the model stored in, and analyzed by, a computer. No longer limited to two-dimensional representations of physical objects, geometric modeling now topologically achieves and analytically completes three-dimensional models. Such models allow users to quickly and automatically derive any geometric property or attribute that the object is likely to possess.
Appearance not being the sole concern, careful distinctions between analytical models and rendering are drawn. Geometric modeling involves a mathematical setting that allows relationships between models to be calculated, for example, closest approach, intersections, shadowing, and so on. In many situations, arbitrary shapes must be represented, such as shapes that do not have special names and whose characteristics are not well defined.
Geometric modeling has three closely-related, yet distinct aspects, which are as follows: (1) representation, where the physical shape of an object is given and presumed to be fixed; (2) design, where a new shape is created to satisfy some operational or aesthetic objectives; and (3) rendering, where an image of the model is needed to visually interpret it.
A geometric-modeling system typically comprises the geometric-modeling software (including the model builder), a computer (anywhere from mainframe to micro), a user interface device (usually graphic), a data base for storing the model and a display generator for creating the graphic output, and usually an array of application programs.
Techniques for modeling, such as B-spline curves and Bezier curves, are effective interactive design tools currently used in industry. Some basic facts and formulas with respect to Bezier curves and surfaces are outlined below for background information. However, readers unfamiliar with these concepts may reference a book entitled "Computer Aided Geometric Design" by G. Farin, published by Academic Press, 1988.
Specifically, with respect to Bezier forms, it should be noted that a degree d Bezier curve is defined by: ##EQU1## where t.epsilon.[0,1], and the points b.sub.i form the Bezier control polygon. To simplify notation, a Bezier curve is identified by its control polygon represented as the row vector below: EQU B(t).ident.[b.sub.0,b.sub.1, . . . ,b.sub.d ].
The derivative of a Bezier degree d curve [b.sub.0, b.sub.1, . . . , b.sub.d ] is the degree d-1 curve set forth below: EQU d[b.sub.1 -b.sub.0,b.sub.2 -b.sub.1, . . . ,b.sub.d -b.sub.d-1 ].
The product of a pair of Bezier curves set forth below: EQU [a.sub.0,a.sub.1, . . . ,a.sub.m ][b.sub.0,b.sub.1, . . . ,b.sub.n ]=[c.sub.0,c.sub.1, . . . ,c.sub.m+n ]
is computed by: ##EQU2## where the summation is taken over all j and k that sum to i such that 0.ltoreq.j.ltoreq.m and 0.ltoreq.k.ltoreq.n.
A degree d Bezier curve [b.sub.0, b.sub.1, . . . b.sub.d ] can be equivalently represented by a degree d+1 Bezier curve [c.sub.0, c.sub.1, . . . , c.sub.d+1 ] by degree raising, where: ##EQU3##
Now taking into consideration Bezier surfaces, note that a degree d Bezier triangle B(u,v) is defined below (this definition differs slightly from the more symmetric version that makes use of barycentric coordinates discussed in "Computer Aided Geometric Design" by G. Farin): ##EQU4## where i, j, and k are non-negative integers that sum to d, (1-u-v),u, v.epsilon.[0,1], and ##EQU5## is the trinomial coefficient ##EQU6## and b.sub.ijk are a triangular array of control points called the Bezier control net. A degree 3 (cubic) Bezier triangle and its control net are illustrated in FIG. 3.
The derivative of a degree d Bezier triangle with respect to a parametric direction w, with coordinates (w.sub.u, w.sub.v), is a degree d-1 Bezier triangle B.sup.w with control points: EQU (-w.sub.u -w.sub.v)b.sub.i+1,j,k +w.sub.u b.sub.i,j+1,k +w.sub.v b.sub.i,j,k+1,
where
i+j+k=d-1.
The edges of a degree d of Bezier triangle B are degree d Bezier curves. For example, the edge corresponding to v=0 is the Bezier curve [b.sub.d,0,0, b.sub.d-1,1,0, . . . b.sub.0,d,0 ]. Similarly, the derivatives along the edge of a Bezier triangle are also Bezier curves. For example, the derivative in the u direction along the edge v=0 is defined by the following Bezier curve: EQU B.sup.u =d[b.sub.d-1,1,0 -b.sub.d,0,0, . . . , b.sub.0,d,0 -b.sub.1,d-1,0 ] .
Similarly, the derivative in the v direction along the edge v=0 is defined by the following Bezier curve: EQU B.sup.v =d[b.sub.d-1,0,1 -b.sub.d,0,0, . . . , b.sub.0,d-1,1 -b.sub.1,d-1,0 ].
Since differentiation is linear, all other derivatives corresponding to the edge v=0 can be found as linear combinations of B.sup.u and B.sup.v. Thus, B.sup.u and B.sup.v span the tangent plane of B, along the edge where v=0. In geometric modeling, this is the key to joining patches smoothly together.
Now addressing the G.sup.1 continuity of Bezier triangles, it should be noted that a surface is considered smooth if, at all points, it has a continuous and well-defined tangent plane. This condition is known as first order geometric continuity and is denoted by G.sup.1. For example, let P and P' be a pair of Bezier triangles that share a common boundary curve. Let u represent the parametric direction corresponding to the pre-image of the common boundary curve. Let t and t' be a pair of parametric directions pointing into the domains of P and P', relative to the common edge. Patches P and P' meet with G.sup.1 continuity, if an only if, there exist functions .phi., .rho., and .tau., such that at all points along an edge of P and P', the following equations hold: EQU P=P' 1. EQU .phi.P.sup.u =.rho.P.sup.t +.tau.P.sup.t' 2. EQU .rho..tau.&gt;0 3. EQU P.sup.v .times.P.sup.t .noteq.0 4.
Condition 1 provides that P and P' share a common boundary curve. This condition, also known as C.sup.0 or G.sup.0 continuity, is satisfied only if the control points of P and P' corresponding to the common boundary curve are identical. Condition 2 indicates that derivatives of P and P' at all points of the common boundary curves are linearly dependent and hence span a common tangent plane. Condition 3 ensures that P and P' lie on opposite sides of the common boundary curve. Condition 4 requires that P and P' be non-degenerate along the common boundary curve. If functions .phi., .rho., and .tau. are constant, P and P' meet with parametric continuity denoted by C.sup.1.
Expanding on additional background information, it should be noted that box splines are a type of multivariate spline function. In the bivariate setting, a box spline is of the form: ##EQU7## where the d.sub.ij are a rectangular array of control points, and N.sup..alpha. is a locally supported, piecewise, polynomial, basis function identified by the tuple of positive integers .alpha.. The length of .alpha. indicates some number of grid directions over which the box spline is defined. The value of each element of .alpha. represents the number of unit pulse convolutions in each of the directions needed to generate the box spline.
One such prior art spline technique is a four directional box spline N.sup.1111. This box spline is piecewise, quadratic, and meets with parametric continuity C.sup.1. A collection of scalar values (.times.1/16) representing the basis function N.sup.1111 in triangular Bezier form is shown in FIG. 4. For further discussion on how to compute the Bezier form of box splines, reference C. Chui and J. J. Lai, "Algorithms for Generating b-nets and Graphically Displaying Spline Surfaces on Three- and Four-Directional Meshes," Computer Aided Geometric Design, vol. 8, pp. 479-93, 1991.
The Bezier form of a box spline basis function implies a geometric construction for the Bezier control nets of the surface. In the case of the box spline N.sup.1111, four quadratic Bezier triangles are constructed corresponding to each vertex of the box spline control mesh. The control points of these patches are computed by taking a succession of midpoints as illustrated in FIGS. 4 and 5.
Having discussed some basic techniques used in geometric modeling, known to those skilled in the art, it should be recognized that modeling smooth free-form shapes using B-splines is severely limited by the requirement that the control mesh have a regular rectangular structure. To overcome this difficulty, methods for generating smooth surfaces over irregular meshes have been developed. However, as yet, none of these methods has matched the efficiency and elegance achieved by B-splines.
Over the years, several techniques for generating B-spline like surfaces over irregular control meshes have been proposed and implemented. In the late 1970's, Doo & Sabian (see D. Doo, "A subdivision algorithm for smoothing down irregular shaped polyhedrons," In Proceedings on Interactive Techniques in Computer Aided Design, pages 157-165, Bologna, 1978) and Catmull & Clark (see E. Catmull and J. Clark, "Recursively generated B-spline surfaces on arbitrary topological meshes," Computer Aided Design, 10(6):350-355, 1978) proposed recursive subdivision surfaces.
These techniques generate smooth surfaces by repeatedly subdividing, or refining an irregular control mesh to create a new mesh with more vertices, faces and edges than the original. At its limit, the refined control mesh converges to a smooth surface (see D. Doo and M. Sabin, "Behavior of recursive division surfaces near extraordinary points. Computer Aided Design, 10(6):356-360, 1978. However, subdivision surfaces cannot be easily analyzed, i.e., they cannot be described in closed form. This complicates analysis of these surfaces as well as analysis of subsequent modeling techniques that deal with them.
Others have proposed parametric, patch-based, spline modeling techniques for approximating irregular control meshes. Chiyokura & Kimura (see H. Chiyokura and F. Kimura, "Design of solids with free-form surfaces," Computer Graphic, 17(3):289-298, 1983) developed a scheme based on Gregory patches that are easy to join together smoothly, but contain singularities at patch vertices.
Van Wijk and others (see, T. N. T. Goodman, "Closed biquadratic surfaces," Constructive Approximation, 7(2):149-160, 1991; S. L. Lee and A. A. Majid, "Closed smooth piecewise bicubic surfaces," ACM Transactions on Graphics, 10(4):342-365, 1991; and J. van Wijk, "Bicubic patches for approximately non-rectangular control-point meshes," Computer Aided Geometric Design, 3(1):1-13, 1986) have presented techniques that approximate a restricted class (where the number of edges surrounding a face or vertex is constrained) of closed polyhedra with bicubic patches.
Other techniques that approximate restricted meshes with parametric surface patches have been proposed by C. Loop and T. DeRose, (see C. Loop and T. DeRose, "Generalized B-spline Surfaces of arbitrary topology," Computer Graphics, 24(4):347-356, 1990) and J. Peters (see J. Peters, "Smooth interpolation of a mesh of curves," Constructive Approximation, 7:221-246, 1991).
The inventor, himself, C. Loop, has proposed (see C. Loop, "Generalized B-spline Surfaces of Arbitrary Topological Type," PhD theseis, university of Washington, 1992) an unrestricted control mesh approximated with n-sided parametric S-patches (see C. Loop and T. DeRose, "A multisided generalization of Bezier surface," ACM Transactions on Graphics, 8(3):204-234, Jul. 1989). Although S-patches have many desirable mathematical properties, manipulating them may require excessive amounts of time and storage space as the number of sides increases.
More recently, Bajaj & Ihm (see C. Bajaj and I. Ihm, "Smoothing polyhedra using implicit algebraic splines," Computer Graphics, 26(2):79-88, 1992) have proposed a technique for interpolating an irregular triangular mesh based on algebraic surfaces. While the degree of these surfaces is low (cubic), there is significant overhead in computing coefficients and rendering.
Thus, there is an ongoing need for improved modeling techniques for generating aesthetically pleasing and realistic images, both effectively and efficiently, to satisfy the growing demands in the computer graphics field.